#ifndef GAMEENGINE_GEOMETRY_TOPOLOGY_HALFEDGE_TRGL_MESH_HPP
#define GAMEENGINE_GEOMETRY_TOPOLOGY_HALFEDGE_TRGL_MESH_HPP

#include <GameEngine/Core/Memory/memory_manager.h>

#ifdef GAMEENGINE_NAMESPACES
namespace GameEngine {
#endif

//=================================================================================
// Implementation of the HalfEdgeTrglMesh class

//! Default constructor
/*!
 *  Create an empty mesh
 */
template <class T>
HalfEdgeTrglMesh<T>::HalfEdgeTrglMesh() {}

//! Destructor
/*!
 *  Free the memory associted to the elements of the mesh (half-edges, faces and vertices)
 */
template <class T>
HalfEdgeTrglMesh<T>::~HalfEdgeTrglMesh() {}

//! Add a triangle face to the mesh
/*!
 *  This function does not check if a face made of these three vertices already exists, nor
 *  if the orientation of the face is consistent with the other faces. The client code is
 *  responsible for checking the consistency of the triangle prior to calling this function.
 *
 @param v1 The first vertex of the triangle
 @param v2 The second vertex of the triangle
 @param v3 The third vertex of the triangle
 @return A pointer to the face that was created
 */
template <class T>
HalfEdgeFace<T>* HalfEdgeTrglMesh<T>::add_triangle(const T& v1, const T& v2, const T& v3) {
	// Find or create the vertices in the mesh
	HalfEdgeVertex<T>* hv1 = add_or_find_vertex(v1);
	HalfEdgeVertex<T>* hv2 = add_or_find_vertex(v2);
	HalfEdgeVertex<T>* hv3 = add_or_find_vertex(v3);

	// Create virtual border half-edges for the triangle
	HalfEdge<T>* oe1 = MemoryManager::instance()->allocate< HalfEdge<T> >(); oe1->set_origin(hv1);
	HalfEdge<T>* oe2 = MemoryManager::instance()->allocate< HalfEdge<T> >(); oe2->set_origin(hv3);
	HalfEdge<T>* oe3 = MemoryManager::instance()->allocate< HalfEdge<T> >(); oe3->set_origin(hv2);

	// Create half-edge face
	HalfEdgeFace<T>* face = MemoryManager::instance()->allocate< HalfEdgeFace<T> >();

	// Create half-edges for the triangle
	HalfEdge<T>* e1 = MemoryManager::instance()->allocate< HalfEdge<T> >(); e1->set_origin(hv1); e1->set_face(face);
	HalfEdge<T>* e2 = MemoryManager::instance()->allocate< HalfEdge<T> >(); e2->set_origin(hv2); e2->set_face(face);
	HalfEdge<T>* e3 = MemoryManager::instance()->allocate< HalfEdge<T> >(); e3->set_origin(hv3); e3->set_face(face);

	// Check vertices half-edges
	if ( hv1->leaving_edge() == nil ) hv1->set_leaving_edge(e1);
	if ( hv2->leaving_edge() == nil ) hv2->set_leaving_edge(e2);
	if ( hv3->leaving_edge() == nil ) hv3->set_leaving_edge(e3);

	// Set opposite faces
	e1->set_opposite_edge(oe3, true);
	e2->set_opposite_edge(oe2, true);
	e3->set_opposite_edge(oe1, true);

	// Create face circle
	e1->set_next_edge(e2);
	e2->set_next_edge(e3);
	e3->set_next_edge(e1);

	// Set face edge
	face->set_edge(e1);

	// Add half-edges and face to the mesh
	edges_.push_back(e1);
	edges_.push_back(e2);
	edges_.push_back(e3);
	edges_.push_back(oe1);
	edges_.push_back(oe2);
	edges_.push_back(oe3);
	faces_.push_back(face);

	// Return created face
	return face;
}

//! Find a triangle face in the mesh
/*!
 *  This function is pretty costly and should therefore be used sparingly whenever
 *  performance does matter
 *
 @param v1 The first vertex of the triangle
 @param v2 The second vertex of the triangle
 @param v3 The third vertex of the triangle
 @return A pointer to the face that was found (may be nil if there is no such face)
 */
template <class T>
HalfEdgeFace<T>* HalfEdgeTrglMesh<T>::find_triangle(const T& v1, const T& v2, const T& v3) const {
	// Find or create the vertices in the mesh
	HalfEdgeVertex<T>* hv1 = find_vertex(v1);
	HalfEdgeVertex<T>* hv2 = find_vertex(v2);
	HalfEdgeVertex<T>* hv3 = find_vertex(v3);
	if ( hv1 == nil ) return nil;
	if ( hv2 == nil ) return nil;
	if ( hv3 == nil ) return nil;

	// Get faces around vertices
	std::list< HalfEdgeFace<T>* > f1 = hv1->faces_around_vertex();
	std::list< HalfEdgeFace<T>* > f2 = hv2->faces_around_vertex();
	std::list< HalfEdgeFace<T>* > f3 = hv3->faces_around_vertex();

	// Iterate over the faces to find a shared one
	// Iterate over the faces sharing the first vertex
	for ( std::list< HalfEdgeFace<T>* >::iterator it1 = f1.begin(); it1 != f1.end(); ++it1 ) {
		// Iterate over the faces sharing the second vertex
		for ( std::list< HalfEdgeFace<T>* >::iterator it2 = f2.begin(); it2 != f2.end(); ++it2 ) {
			// Test if both faces are the same
			if ( (*it1) != (*it2) ) continue;

			// Iterate over the faces sharing the third vertex
			for ( std::list< HalfEdgeFace<T>* >::iterator it3 = f3.begin(); it3 != f3.end(); ++it3 ) {
				if ( (*it1) == (*it3) ) return (*it1);
			}
		}
	}

	// No such face could be found
	return nil;
}

//! Insert a vertex in this triangle
/*!
 *  This function provides a way to subdivide the triangle into three sub-triangles.
 *
 *  Please note that the insertion of vertices whose locations already existed in the mesh
 *  is forbidden.
 *
 @param vertex The vertex to insert in the triangle
 @param trgl The triangle in which vertex should be inserted
 @return A pointer to the vertex that was created. May be nil if vertex could not be
         inserted (i.e., if such a vertex already existed in the mesh, or if the face
		 is not a triangle)
 */
template <class T>
HalfEdgeVertex<T>* HalfEdgeTrglMesh<T>::insert_vertex(const T& vertex, HalfEdgeFace<T>& trgl) {
	// Get the three half-edges that define the triangle and check if they define a triangle
	HalfEdge<T>* e1 = trgl.edge(); if ( e1 == nil ) return nil;
	HalfEdge<T>* e2 = e1->next_edge(); if ( e2 == nil ) return nil;
	HalfEdge<T>* e3 = e2->next_edge(); if ( e3 == nil ) return nil;
	if ( e3->next_edge() != e1 ) return nil;

	// Try to find the vertex in the mesh
	HalfEdgeVertex<T>* v = find_vertex(vertex);
	if ( v != nil ) return nil;

	// Create the vertex in the mesh
	v = add_vertex(vertex);

	// Create three half-edges that originate from the vertex
	HalfEdge<T>* oe1 = MemoryManager::instance()->allocate< HalfEdge<T> >();
	HalfEdge<T>* oe2 = MemoryManager::instance()->allocate< HalfEdge<T> >();
	HalfEdge<T>* oe3 = MemoryManager::instance()->allocate< HalfEdge<T> >();
	oe1->set_origin(v);
	oe2->set_origin(v);
	oe3->set_origin(v);
	v->set_leaving_edge(oe1);
	edges_.push_back(oe1);
	edges_.push_back(oe2);
	edges_.push_back(oe3);

	// Create three opposite half-edges
	HalfEdge<T>* ooe1 = MemoryManager::instance()->allocate< HalfEdge<T> >();
	HalfEdge<T>* ooe2 = MemoryManager::instance()->allocate< HalfEdge<T> >();
	HalfEdge<T>* ooe3 = MemoryManager::instance()->allocate< HalfEdge<T> >();
	ooe1->set_origin(e1->origin());
	ooe2->set_origin(e2->origin());
	ooe3->set_origin(e3->origin());
	edges_.push_back(ooe1);
	edges_.push_back(ooe2);
	edges_.push_back(ooe3);

	// Set opposite edges
	oe1->set_opposite_edge(ooe1, true);
	oe2->set_opposite_edge(ooe2, true);
	oe3->set_opposite_edge(ooe3, true);

	// Set next edges
	e1->set_next_edge(ooe2);
	e2->set_next_edge(ooe3);
	e3->set_next_edge(ooe1);
	oe1->set_next_edge(e1);
	oe2->set_next_edge(e2);
	oe3->set_next_edge(e3);
	ooe1->set_next_edge(oe3);
	ooe2->set_next_edge(oe1);
	ooe3->set_next_edge(oe2);

	// Set faces
	HalfEdgeFace<T>* trgl2 = MemoryManager::instance()->allocate< HalfEdgeFace<T> >();
	HalfEdgeFace<T>* trgl3 = MemoryManager::instance()->allocate< HalfEdgeFace<T> >();
	faces_.push_back(trgl2);
	faces_.push_back(trgl3);

	// Set face edges
	trgl.set_edge(e1);
	trgl2->set_edge(e2);
	trgl3->set_edge(e3);

	// Return vertex
	return v;
}

//=================================================================================

#ifdef GAMEENGINE_NAMESPACES
} // namespace GameEngine
#endif

#endif
